We present a strongly exponential lower bound that applies both to the subsetsynchronization threshold for binary deterministic automata and to the carefulsynchronization threshold for binary partial automata. In the later form, theresult finishes the research initiated by Martyugin (2013). Moreover, we showthat both the thresholds remain strongly exponential even if restricted tostrongly connected binary automata. In addition, we apply our methods tocomputational complexity. Existence of a subset reset word is known to bePSPACE-complete; we show that this holds even under the restriction to stronglyconnected binary automata. The results apply also to the correspondingthresholds in two more general settings: D1- and D3-directable nondeterministicautomata and composition sequences over finite domains.
展开▼
